Ancestral graphs can encode conditional independence relations that arise indirected acyclic graph (DAG) models with latent and selection variables.However, for any ancestral graph, there may be several other graphs to which itis Markov equivalent. We state and prove conditions under which two maximalancestral graphs are Markov equivalent to each other, thereby extendinganalogous results for DAGs given by other authors. These conditions lead to analgorithm for determining Markov equivalence that runs in time that ispolynomial in the number of vertices in the graph.
展开▼